A dictionary compression scheme maintains a list of sequences within the uncompressed data. Compression replaces these sequences with a code.
You get the most compression when the dictionary sequences are long and frequently repeated.
Problem: How do you transmit the dictionary with the compressed data?
Three variants based on work by Abraham Lempel and Jacob Zev.
LZ77:
LZ78:
LZW: Described by Terry Welsh in 1984.
For 8-bit values, initialize the 256 dictionary entries to these values. Scan the data, reading from the input stream until it no longer matches a dictionary entry. Output the code for the longest matching string. Set a new dictionary code by appending the non-matched character to the matching string.
Miano Fig 12.5
For GIF, the initial code size is usually set to 9 bits. Code size is increased by 1 bit as needed. 12 bits is the maximum code size; the data dictionary will not get bigger than 4096 entries.
LZW can be decoded without having the dictionary. Both the encoder and the decoder start with a dictionary containing 0 to 255. These will be the first codes transmitted. When the decoder sees a number higher than 255, it can build the dictionary the same way that the encoder did.
LZW is lossless symmetric compression. It almost always gets better compression than RLE. Efficient implementation can be difficult.
In GIF, codes are stored with the least significant bit first.
Originally developed by CompuServe
Several bitmap images may be in one file; this is seldom done except for animations.
Usually 16 or 256 colors.
GIF files are stream-based, organized as data packets (called “blocks”).
The different blocks may be in different orders.
GIF image data is always LZW compressed.
Two versions, both commonly used: GIF87a, GIF89a.
See figures 12.1 and 12.3 of Miano.
|
Header & Screen
Descriptor |
|
Global Color table
(Palette) |
|
Extension block (89a only) |
|
Image 1 |
|
Image 2 |
|
… |
|
Image n |
|
Trailer |
typedef struct _GifHeader
{
// Header
BYTE
Signature[3]; /* 0x00 Header
Signature (always "GIF") */
BYTE Version[3]; /* 0x03 GIF format version("87a" or
"89a") */
// Logical
Screen Descriptor
WORD
ScreenWidth; /* 0x06 Width of
Display Screen in Pixels */
WORD
ScreenHeight; /* 0x08 Height of
Display Screen in Pixels */
BYTE
Packed; /* 0x0A Screen and
Color Map Information
Bits 0-2 Size of the
Global Color Table
Bit 3 Color Table Sort
Flag
Bits 4-6 Color Resolution
Bit 7 Global Color Table
Flag */
BYTE
BackgroundColor; /* 0x0B Background
Color Index
The background is the area
not covered by the image. */
BYTE
AspectRatio; /* 0x0C Pixel Aspect
Ratio */
} GIFHEAD;
typedef struct _GifGraphicsControlExtension
{ /* version
89a only */
BYTE
Introducer; /* Extension Introducer
(always 21h) */
BYTE
Label; /* Graphic Control Label (always F9h) */
BYTE
BlockSize; /* Size of remaining
fields (always 04h) */
BYTE
Packed; /* Method of graphics
disposal to use
Bit 0 Transparent Color
Flag
Bit 1 User Input Flag
Bits 2-4 Disposal Method
00h (disposal method not specified),
01h (do not dispose of graphic),
02h (overwrite graphic with background color),
04h (overwrite graphic with previous graphic).
Bits 5-7 Reserved */
WORD
DelayTime; /* Hundredths of seconds
to wait */
BYTE ColorIndex; /* Transparent Color Index */
BYTE
Terminator; /* Block Terminator
(always 0) */
} GIFGRAPHICCONTROL;
typedef struct _GifImageDescriptor
{
BYTE
Separator; /* Image Descriptor
identifier; always 0x2C */
WORD
Left; /* X position of image on
the display */
WORD
Top; /* Y position of image on
the display */
WORD
Width; /* Width of the image in
pixels */
WORD
Height; /* Height of the image in
pixels */
BYTE
Packed; /* Image and Color Table
Data Information
Bit 7 Local Color Table
Flag
Bit 6 Interlace Flag
Bit 5 Sort Flag
Bits 3-4 Reserved
Bits 0-2 Size of Local
Color Table Entry*/
} GIFIMGDESC;
Example: Ball.GIF
Header/Version: GIF89a
Width, Height: 14 x 14
Packed: 0xA5 = 1 010 0 101
Color
table size is 2^(5+1) = 64 entries = 192 (0xC0) bytes
Thus
palette is bytes 0x0D through 0xCC.
Bit 3 =
0: Color table is not sorted by importance.
Color
Resolution = 2; Original image had 3 bits / primary color
The
leading bit = 1 to show that there is a global color table.
BackgroundColor = 0; Background color is (AF, AF,
AF) light gray.
AspectRatio = 0 for square pixels.
The extension block starts at 0xCD:
21 F9 04 01 00 00 00 00
The first 3 bytes are the proper fixed values.
The set LSB of byte 4 says that the 7th
byte (value 0) is an index for a transparent color.
The image starts at 0xD5 with the local image
descriptor:
2C 00 00 00 00 0E 00 0E 00 00
The image starts at (0, 0) and is size 14 x 14.
There is no local color table.
The image is non-interlaced.
Data sub-blocks start at 0xDF, which shows that
there will be 6 blocks.
102 bytes in the rest of the image.
Let’s edit the Ball.GIF image.
First, let’s change the size of the logical screen, which had been 14 x 14 (at 0x06 and 0x08). We can make it 64 x 64 and save as ball2.gif. [no difference in IE]
Let’s change the background color. This is at location 0x0B and had value 0. The palette starts at 0x0D, which contains (af, af, af). Thus the background color is a light gray Change the background to 0x0a (7b c6 84) [no difference]
Change the starting position from (0,0) to (8, a) (at locations d6 and d8) save as ball4.
No difference in Graph X viewer.
It is different in IE; the ball is at a different position.
No difference in Paint Shop Pro.
No difference in Mosaic.
In Adobe Photoshop, everything is there – changed background color, expanded logical screen, changed position.
[Ball4.clp]
If the interlace bit is set in the packed byte of the local image descriptor table, the order of the scan lines is altered as in figure GIF-2 of Murray & vanRyper.
[scan line table code on p. 440-441 of Murray & vanRyper or p. 178 in Miano]
GIF is data stream oriented. Unlike BMP and PCX, you never need to jump around in the file using offsets.
The stream is split into blocks.
[Figure GIF-3 of Murray & vanRyper]
Blocks start with the following separator codes:
0x21 89a Extension block. The second byte is a type code:
0x01 Plain text extension
0xf9 Graphic control extension
0xfe Comment extension
0xff Application extension
0x2C Image block
0x3B GIF terminator
The Plain Text Extension block is 15 bytes in length and has the
following structure:
typedef struct _GifPlainTextExtension
{
BYTE
Introducer; /* Extension
Introducer (always 21h) */
BYTE
Label; /* Extension Label
(always 01h) */
BYTE
BlockSize; /* Size of Extension
Block (always 0Ch) */
WORD
TextGridLeft; /* X position of
text grid in pixels */
WORD
TextGridTop; /* Y position of
text grid in pixels */
WORD
TextGridWidth; /* Width of the text
grid in pixels */
WORD
TextGridHeight; /* Height of the
text grid in pixels */
BYTE
CellWidth; /* Width of a grid
cell in pixels */
BYTE
CellHeight; /* Height of a grid
cell in pixels */
BYTE
TextFgColorIndex; /* Text foreground
color index value */
BYTE TextBgColorIndex; /* Text background color index value */
} GIFPLAINTEXT;
BYTE
PlainTextData[]; /* The Plain Text
data block */
BYTE
Terminator; /* Block Terminator
(always 0) */
typedef struct _GifCommentExtension
{
BYTE
Introducer; /* Extension Introducer
(always 21h) */
BYTE
Label; /* Comment Label (always
FEh) */
BYTE
CommentData[]; /* The Comment Text
data block.
Comment
Data - Sequence of sub-blocks, each of size at most
255 bytes and at least 1 byte, with the size in a byte preceding
the data. The end of the
sequence is marked by the Block
Terminator. */
BYTE
Terminator; /* Block Terminator
(always 0) */
} GIFCOMMENT;
typedef struct _GifApplicationExtension
{
BYTE
Introducer; /* Extension
Introducer (always 21h) */
BYTE
Label; /* Extension Label
(always FFh) */
BYTE
BlockSize; /* Size of Extension
Block (always 0Bh) */
CHAR
Identifier[8]; /* Application
Identifier */
BYTE
AuthentCode[3]; /* Application
Authentication Code */
} GIFAPPLICATION;
BYTE
ApplicationData[]; /* Application Data
sub-blocks */
BYTE
Terminator; /* Block Terminator
(always 0) */
Animation is done with an
application extension as follows:
GIFAPPLICATION animate
{
Introducer
= 0x21;
Label =
0xFF;
BlockSize =
11;
Identifier
= “NETSCAPE”; /* not correct code;
string
has no zero terminator
This
should work on all browsers. */
AuthentCode[3] = ‘2’, ‘.’, ‘0’;
};
BYTE
BlockSize = 3;
BYTE
ExtensionType = 1;
WORD
RepeatCount; /* Number of times the
animation repeats
0
to replay indefinitely. */
BYTE
Terminator = 0;
The graphics control extension only affects the image that immediately follows it.
For animation, you should put a graphics control extension in front of each image.
Concatenate Ball3.GIF and Ball4.GIF to form Ball5.GIF
We eliminate:
Terminator on the 1st image (at 0x145)
Header and screen descriptor for 2nd image (0x146-0x152)
Global color table for 2nd image (0x153-0x212)
The following information is the graphics control extension for the 2nd image.
21 F9 04 01 00 00 00 00
We will change it to wait 2 seconds (200 = 0xc8):
21 F9 04 01 c8 00 00 00
[Change byte at 149]
The packed byte had been 01
Bit 0 Transparent Color
Flag
Bit 1 User Input Flag
Bits 2-4 Disposal Method
0 No action,
1 Leave the image in place,
2 Restore the background color,
3 (or 4?) Restore what was there before.
Bits 5-7 Reserved */
We will set that to binary 0000 1001 = 0x09 to overwrite the graphic with the background color:
21 F9 04 09 c8 00 00 00
[Change byte at 148]
We will also make these changes to the first graphic control block at D0 and D1.
Save this and look at it with IE.
Add an application extension to repeat 5 times:
21 ff 0b “NETSCAPE2.0” 03 01 05 00 00
Put this at 0xCD, in front of the first graphics control extension block.